//
// Created by spiro on 19-4-16.
//
#include <stdio.h>
#include <stdlib.h>
#include "bin_tree.h"


bool IsEmpty(BinTree * tree) {
    return (tree->size == 0);
}

void TreeInitialized(BinTree * tree) {
    tree->root = NULL;
    tree->size = 0;
}

static void InorderWalk(BTNode * node, void (*func)(Key)) {
    if (node == NULL) {
        return;
    }
    
    BTNode * left = node->left;
    BTNode * right = node->right;

    InorderWalk(left, func);
    (*func)(node->key);
    InorderWalk(right, func);
}

void TreeInorderWalk(BinTree * tree, void (*func)(Key)) {
    if (IsEmpty(tree)) {
        return;
    }
    
    BTNode * root = tree->root;
    InorderWalk(root, func);
}

BTNode * TreeSearch(BinTree * tree, Key key) {
    if (IsEmpty(tree)) {
        return NULL;
    }

    BTNode * node = tree->root;
    int ret;

    while(node != NULL){
        ret = KeyCompare(key, node->key);
        if (ret == 0) {
            return node;
        }

        if (ret < 0) {
            node = node->left;
        } else {
            node = node->right;
        }
        
    }
    return node;
}

/**
 * Get minimum node pointer in tree [node] as root
 */
static BTNode * Minimum(BTNode * node) {
    BTNode * p = NULL;

    while(node != NULL){
        p = node;
        node = node->left;
    }

    return p;
}

/**
 * Get maximum node pointer in tree [node] as root
 */
static BTNode * Maximum(BTNode * node) {
    BTNode * p = NULL;

    while(node != NULL){
        p = node;
        node = node->right;
    }

    return p;
}

BTNode * TreeMinimum(BinTree * tree) {
    if (IsEmpty(tree)) {
        return NULL;
    }

    return Minimum(tree->root);
}

BTNode * TreeMaximum(BinTree * tree) {
    if (IsEmpty(tree)) {
        return NULL;
    }

    return Maximum(tree->root);
}

BTNode * TreePredecessor(BTNode * node) {
    if (node == NULL) {
        return NULL;
    }
    
    if (node->left != NULL) {
        return Maximum(node->left);
    }

    BTNode * parent = node->parent;
    while(parent != NULL && parent->left == node){
        node = parent;
        parent = node->parent;
    }
    
    return parent;
}

BTNode * TreeSuccessor(BTNode * node) {
    if (node == NULL) {
        return NULL;
    }
    
    if (node->right != NULL) {
        return Minimum(node->right);
    }

    BTNode * parent = node->parent;
    while(parent != NULL && parent->right == node){
        node = parent;
        parent = node->parent;
    }
    
    return parent;
}

static BTNode * NewBTNode(Key key) {
    BTNode * node = (BTNode *)malloc(sizeof(BTNode));
    if (node != NULL) {
        node->key = key;
        node->parent = NULL;
        node->left = NULL;
        node->right = NULL;
    }
    return node;
}

BTNode * TreeInsert(BinTree * tree, Key key) {
    if (IsEmpty(tree)) {
        BTNode * root = NewBTNode(key);
        if (root != NULL) {
            tree->root = root;
            tree->size = 1;
        }        
        return root;
    }

    BTNode * p;
    BTNode * node = tree->root;
    int ret;

    while(node != NULL){
        ret = KeyCompare(key, node->key);
        p = node;
        if (ret > 0) {
            node = p->right;
        } else {
            node = p->left;
        }
    }
    
    BTNode * newNode = NewBTNode(key);
    newNode->parent = p;
    if (ret > 0) {
        p->right = newNode;
    } else {
        p->left = newNode;
    }

    tree->size++;
    return newNode;
}

/**
 * replace subtree(u as root) by subtree(v as root), u's parent become v's parent.
 */
static void Transplant(BinTree * tree, BTNode * u, BTNode * v) {
    if (u->parent == NULL) {
        tree->root = v;
    } else if (u == u->parent->left) {
        u->parent->left = v;
    } else {
        u->parent->right = v;
    }
    
    if (v != NULL) {
        v->parent = u->parent;
    }
}

void TreeDelete(BinTree * tree, BTNode * node) {
    if (node->left == NULL) {
        Transplant(tree, node, node->right);
    } else if (node->right == NULL) {
        Transplant(tree, node, node->left);
    } else {
        BTNode * y = Minimum(node->right);
        if (y->parent != node) {
            Transplant(tree, y, y->right);
            y->right = node->right;
            node->right->parent = y;
        }
        
        Transplant(tree, node, y);
        y->left = node->left;
        node->left->parent = y;
    }
    tree->size--;
    free(node);
}


static void release(BTNode * node) {
    if (node == NULL) {
        return;
    }
    release(node->left);
    release(node->right);
    free(node);
}

void TreeRelease(BinTree * tree) {
    release(tree->root);
    tree->root = NULL;
    tree->size = 0;
}